package algorithm.swordoff;

/**
 * 矩阵中的路径
 * 在表格中dfs找是否存在给定单词
 */

public class SQ12 {

    public boolean exist(char[][] board, String word) {
        boolean total = false;

        // 注意需要遍历每个位置为起始去搜索,不能简单的写成return dfs(...)
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                total |= dfs(board, word, i, j, "", new boolean[board.length][board[0].length]);
            }
        }

        return total;
    }

    /**
     * 有三种情况需要剪枝(返回false),一个是查找坐标超出越界,一个是curr和target前面同样长度不匹配,还有个是搜索过了
     * 怎么在递归中返回值,这是个很好的例子(中间创建一个变量,递归回退的时候返回这个变量)
     *
     * @param board      常量,输入路径字符二维表
     * @param target     常量C,需要形成的路径字符串,用来判断递归终点
     * @param row        变量V,当前所在位置行数
     * @param column     变量V,当前所在位置列数
     * @param curr       变量V,当前已经组成的路径字符串,用来判断递归终点和剪枝
     * @param isSearched 变量V,深度优先搜索的搜索过的二维表
     * @return
     */
    private boolean dfs(char[][] board,
                        String target,
                        int row,
                        int column,
                        String curr,
                        boolean[][] isSearched) {

        if (row < 0 || row >= board.length || column < 0 || column >= board[0].length) return false;
        else if (isSearched[row][column]) return false;
        else {
            curr = curr + board[row][column];
            // 匹配结束
            if (target.equals(curr)) return true;

            // 没匹配完
            else {
                if (!curr.equals(target.substring(0, curr.length()))) return false;  // curr和target的前缀不匹配,剪枝
                else {
                    boolean tempJudement = false;
                    isSearched[row][column] = true;
                    tempJudement = dfs(board, target, row, column - 1, curr, isSearched) ||
                            dfs(board, target, row - 1, column, curr, isSearched) ||
                            dfs(board, target, row + 1, column, curr, isSearched) ||
                            dfs(board, target, row, column + 1, curr, isSearched);
                    isSearched[row][column] = false;
                    return tempJudement;
                }
            }
        }
    }

    public static void main(String[] args) {
        char[][] a = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        SQ12 sq12 = new SQ12();
        System.out.println(sq12.exist(a, "BC"));

    }
}
